package com.learn.algorithm.realize;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * LRU: 最近最少使用算法 。 最近最少使用的元素，在接下来一段时间内，被访问的概率也很低。
 * * 即最近被使用的元素，在接下来一段时间内，被访问概率较高。
 * * <p>
 * * 用链表的结构：
 * * 链表尾表示最近被访问的元素，越靠近链表头表示越早之前被访问的元素
 * * <p>
 * * 插入一个元素，cache 不满，插到链表尾，满，移除cache链头元素再插入链表尾
 * * 访问一个元素，从链表尾部开始遍历, 访问到之后，将其从原位置删除，重新加入链表尾部
 * * <p>
 * * 实现1：用双向链表实现。
 * * put、get 时间复杂度:O(n)       效率低
 *
 * @author wangxing
 * @version 2020/7/9 6:53 Administrator
 */
public class LRULinkedList implements ILRU {
    /**
     * 存放数据的linkedList结构缓存
     */
    private LinkedList<Node> cache;
    /**
     * LRU中存放数据总量
     */
    private int capacity;

    public LRULinkedList(int capacity) {
        this.cache = new LinkedList<>();
        this.capacity = capacity;
    }

    /**
     * 返回最少使用内容
     *
     * @return
     */
    @Override
    public String get(String key) {
        String val = null;
        if (!this.cache.isEmpty()) {
            Iterator<Node> iterator = this.cache.iterator();
            Node temp = null;
            while (iterator.hasNext()) {
                temp = iterator.next();
                if (key.equals(temp.key)) {
                    val = temp.val;
                    iterator.remove();
                    put(key, val);
                    break;
                }
            }
        }
        return val;
    }

    /**
     * @param key
     * @param val
     */
    @Override
    public void put(String key, String val) {
        Iterator<Node> iterator = this.cache.iterator();
        //查看队列中是否已经有当前数据，如果有了就删除，然后重新放入队尾中，提升对象存活概率
        while (iterator.hasNext()) {
            if (key.equals(iterator.next().key)) {
                iterator.remove();
                break;
            }
        }
        //如果当前队列中数据已经达到了我们的总数据数量，则将第一个插入的数据进行删除，空出位置后再进行数据更替
        if (this.capacity == this.cache.size()) {
            this.cache.removeFirst();
        }
        this.cache.add(new Node(key, val));
    }

    private class Node {
        String key;
        String val;

        public Node(String key, String val) {
            this.key = key;
            this.val = val;
        }
    }
}
